package net.tp.algo.maxsubarr;

public class Kadane {

    public final int sum;
    public final int fromIndex;
    public final int toIndex;

    public Kadane(int[] a) {

        int maxValue = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 1; i <= a.length; i++) {
            if (a[i-1] > maxValue) {
                maxValue = a[i-1];
                maxIndex = i;
            }
        }
        if (maxValue <= 0) {
            sum = maxValue;
            fromIndex = maxIndex-1;
            toIndex = maxIndex;
        }
        else {

            int[] length = new int[a.length+1];

            int[] M = new int[a.length+1];

            for (int i = 1; i <= a.length; i++) {
                if (M[i-1] + a[i-1] >= 0) {
                    length[i] = length[i-1] + 1;
                    M[i] = M[i-1] + a[i-1];
                }
            }

            maxIndex = 0;
            maxValue = -1;
            for (int i = 1; i <= a.length; i++) {
                if (M[i] > maxValue && length[i] > 0) {
                    maxIndex = i;
                    maxValue = M[i];
                }
            }

            sum = maxValue;
            fromIndex = maxIndex - length[maxIndex];
            toIndex = maxIndex;

        }
    }
}
